#include "redBlackTree.h"

node * CRedBlackTree::nil = new node(-1, CRedBlackTree::nil);

CRedBlackTree::CRedBlackTree()
{
	root = nil;
}

CRedBlackTree::~CRedBlackTree()
{
	if(root != nil)
		delete root;
}

void CRedBlackTree::insert(int key)
{
	node *z = new node(key, nil);
	z->color = RED;
	if(root == nil)
		root = z;
	else
	{
		node *y = getPositionToInsert(z);
		insertChild(y, z);
	}
	insertFixup(z);
}

node * CRedBlackTree::getPositionToInsert(node *z)
{
	node *y = nil, *x = root;
	while(x != nil)
	{
		y = x;
		if(z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	return y;
}

void CRedBlackTree::insertChild(node *parent, node *child)
{
	child->p = parent;
	if(child->key < parent->key)
		parent->left = child;
	else
		parent->right = child;
	child->left = nil;
	child->right = nil;
}

node *CRedBlackTree::search(int k)  
{  
	return search(root, k);
}

node *CRedBlackTree::search(node *x, int k)  
{  
	if(x == nil || k == x->key)  
        return x;  
    if(k < x->key)  
        return search(x->left, k);  
    else  
        return search(x->right, k);  
}

void CRedBlackTree::remove(node *z)
{
	node * toRemove = findTheNodeToRemove(z);
	node *child = getChild(toRemove);
	if(toRemove != z)
		z->key = toRemove->key;
	removeReally(toRemove);
	if(toRemove->color == BLACK)
		removeFixup(child);
}

node * CRedBlackTree::findTheNodeToRemove(node *z)
{
	if(z->left == nil || z->right == nil)
		return z;
	else 
		return successor(z);
}

void CRedBlackTree::removeReally(node *toRemove)
{
	node *child = getChild(toRemove);
	child->p = toRemove->p;
	if(toRemove->p == nil)
		root = child;
	else if(toRemove == toRemove->p->left)
		toRemove->p->left = child;
	else
		toRemove->p->right = child;

}

node * CRedBlackTree::getChild(node *parent)
{
	if(parent->left != nil)
		return parent->left;
	else 
		return parent->right;
}

node *CRedBlackTree::successor(node *x)  
{  
	if(x->right != nil)  
        return minimum(x->right);  
    node *y = x->p;  
    while(x == y->right)  
    {  
        x = y;  
        y = y->p;  
    }  
    return y;  
}

node *CRedBlackTree::minimum(node *x)  
{  
	while(x->left != nil)  
        x = x->left;  
    return x;  
}

void CRedBlackTree::insertFixup(node *z)
{
	node *y;
	//?????????,??????2???,???????2,????
	while(z->p->color == RED)
	{
		//p[z]?????,?????
		if(z->p == z->p->p->left)
		{
			//?y?z????
			y = z->p->p->right;
			//?????,z???y????
			if(y->color == RED)
			{
				//?p[z]?y????????z?p[z]???????
				z->p->color = BLACK;
				y->color = BLACK;
				//?p[p[z]]?????????5
				z->p->p->color = RED;
				//?p[p[z]]???????z???while??
				z = z->p->p;
			}
			else
			{
				//?????:z???????,?z????
				if(z == z->p->right)
				{
					//?p[z]??,???????
					z = z->p;
					leftRotate(z);
				}
				//?????:z???????,?z????
				//??p[z]?p[p[z]]???,???
				z->p->color = BLACK;
				z->p->p->color = RED;
				rightRotate(z->p->p);
			}
		}
		//p[z]?????,?????,?????
		else if(z->p == z->p->p->right)
		{
			y = z->p->p->left;
			if(y->color == RED)
			{
				z->p->color = BLACK;
				y->color = BLACK;
				z->p->p->color = RED;
				z = z->p->p;
			}
			else
			{
				if(z == z->p->left)
				{
					z = z->p;
					rightRotate(z);
				}
				z->p->color = BLACK;
				z->p->p->color = RED;
				leftRotate(z->p->p);
			}
		}
	}
	//???????
	root->color = BLACK;
}
//??,?y = x->right, ????x?y???????????
//????????:x,y,y->left,?node={p,l,r},??????:
//x={x->p,x->left,y}??{y,x->left,y->left}
//y={x,y->left,y->right}??{x->p,x,y->right}
//y->left={y,y->left->left,y->left->right}??{x,y->left->left,y->left->right}
void CRedBlackTree::leftRotate(node *x)
{
	//?y = x->right
	node *y = x->right;
	//????????????????,?????????
	x->right = y->left;
	if(y->left != nil)
		y->left->p = x;
	y->p = x->p;
	if(x->p == nil)//????:x????
		root = y;
	else if(x == x->p->left)
		x->p->left = y;
	else 
		x->p->right = y;
	y->left = x;
	x->p = y;
}
//??,?y = x->left, ????x?y???????????
//?????????
void CRedBlackTree::rightRotate(node *x)
{
	node *y = x->left;
	x->left = y->right;
	if(y->right != nil)
		y->right->p = x;
	y->p = x->p;
	if(x->p == nil)
		root = y;
	else if(x == x->p->right)
		x->p->right = y;
	else 
		x->p->left = y;
	y->right = x;
	x->p = y;
}
//?????

//??????

//??????,x????????,????????????????
void CRedBlackTree::removeFixup(node *x)
{
	node *w;
	//??????????????????????,??????????,?????????
	while(x != root && x->color == BLACK)
	{
		//?x???????(?????????)
		if(x == x->p->left)
		{
			//?w?x???,??w???,?????????
			//???????x????????,???????x???????
			w = x->p->right;
			//?????:w????
			if(w->color == RED)
			{
				//??w?p[x]???
				w->color = BLACK;
				x->p->color = RED;
				//?p[x]??????
				leftRotate(x->p);
				//?w?x????
				w = x->p->right;
				//??2.3.4??????
			}
			//????:w???,w??????????
			if(w->left->color == BLACK && w->right->color == BLACK)
			{
				//??w?x???
				//w??????,??????,x????????,?????????
				w->color = RED;
				//?p[x]??????
				x = x->p;
				//???x????????,??for??????
			}
			//?????,w????,w->left????,w->right????
			else
			{
				if(w->right->color == BLACK)
				{
					//??w?left[x]???
					w->left->color = BLACK;
					w->color = RED;
					//?w??????
					rightRotate(w);
					//?w?x????
					w = x->p->right;
					//??????????
				}
				//?????:w????,w->left????,w->right????
				//??w?p[x]???
				w->color =x->p->color;
				x->p->color = BLACK;
				w->right->color = BLACK;
				//?p[x]??????
				leftRotate(x->p);
				//????????,?x????????????
				x = root;
			}
		}
		//?x???????(?????????)
		else if(x == x->p->right)
		{
			//?w?x???,??w???,?????????
			//???????x????????,???????x???????
			w = x->p->left;
			//?????:w????
			if(w->color == RED)
			{
				//??w?p[x]???
				w->color = BLACK;
				x->p->color = RED;
				//?p[x]??????
				rightRotate(x->p);
				//?w?x????
				w = x->p->left;
				//??2.3.4??????
			}
			//????:w???,w??????????
			if(w->right->color == BLACK && w->left->color == BLACK)
			{
				//??w?x???
				//w??????,??????,x????????,?????????
				w->color = RED;
				//?p[x]??????
				x = x->p;
				//???x????????,??for??????
			}
			//?????,w????,w->right????,w->left????
			else
			{
				if(w->left->color == BLACK)
				{
					//??w?right[x]???
					w->right->color = BLACK;
					w->color = RED;
					//?w??????
					leftRotate(w);
					//?w?x????
					w = x->p->left;
					//??????????
				}
				//?????:w????,w->right????,w->left????
				//??w?p[x]???
				w->color =x->p->color;
				x->p->color = BLACK;
				w->left->color = BLACK;
				//?p[x]??????
				rightRotate(x->p);
				//????????,?x????????????
				x = root;
			}
		}
	}
	//????????
	x->color = BLACK;
}

bool CRedBlackTree::isNodeNull(node *z)
{
	if (z == nil)
		return true;
	return false;
}
